class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        感觉这种多个不同选择的（但不是很多哈），都可以暴搜 + 剪枝呢。比如这个题每步要么增加一个左括号，要么增加一个右括号，
        是一个二叉的选择，所以暴搜很容易写出来，
        就是dfs(left - 1, right, curStr + "("); dfs(left, right - 1, curStr + ")");
        但是并不是每个分支都是符合要求的（正确的括号匹配），所以加上if来剪枝哈～
        """
        res = []
        self.dfs(res, n, n, '')
        return res

    def dfs(self, res, left, right, path):
        if left == 0 and right == 0:
            res.append(path)
            return
        if left > 0:
            self.dfs(res, left - 1, right, path + '(')
        if left < right:
            self.dfs(res, left, right - 1, path + ')')
'''
需要添加left<right的判断
'''
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def dfs(left,right,strs):
            if not left and not right:
                res.append(strs)
                return
            if left > right:
                return
            if left>0:
                dfs(left-1,right,strs+'(')
            if right >0:
                dfs(left,right-1,strs+')')
        dfs(n,n,'')
        return res